#include<stdlib.h>
#include "SqStack.h"
#include "StringStack.h"
#include "SqQueue.h"


typedef struct 
{
	char data[MAXSIZE];
	int top;
} SqStackChar;

 
void DestroyCharStack(SqStackChar *S){ 				//若栈存在，则销毁它  
	if(S==NULL)
		return;
	free(S);
}

void ClearCharStack(SqStackChar *S){ 				//将栈清空
	if(S==NULL)
		return;

	for(int i=0;i<MAXSIZE;++i){
		S->data[i] = 0;
	}
	S->top = -1;							//栈顶指向最后一位，-1表明栈为空
}
bool CharStackEmpty(SqStackChar S){					//若栈为空，返回true，否则返回false
	if(S.top==-1)
		return true;
	return false;
}

void CharGetTop(SqStackChar *S,char *e){		//若栈存在且非空，用e返回S的栈顶元素
	if(S->top==-1){
		free(e);
		e = NULL;
		return;
	}
	*e = S->data[S->top];
}
void CharPush(SqStackChar *S,char *e){		//若栈S存在，插入新元素e到栈S中并称为栈顶元素  
	if(S==NULL||S->top ==MAXSIZE-1)
		return; 
	S->top++;
	S->data[S->top] = *e; 
}

void CharPop(SqStackChar *S,char *e){			//删除栈S中栈顶元素，并用e返回其值 
	if(S==NULL||S->top==-1)
		return;
	*e = S->data[S->top];
	S->data[S->top] = 0;
	S->top--; 
}
int CharStackLength(SqStackChar S){				//返回栈S的元素个数
	return S.top+1;
} 

int strtodouble(String str,double *num){
	char* p=str;
	double n = 0;
	bool afterDot = false;
	int afterDotCount = 0;
	while(*p!='\0'){
		// printf("%c\n", *p);
		if(*p=='.'){
			afterDot = true;
			afterDotCount = 1;
			p++;
			continue;
		}
		if(!afterDot){
			n = n*10 + *p-48;
		}else{
			double pd =*p-48; 
			double percent = 10;
			for (int i = 1; i < afterDotCount; ++i)
			{
				percent = percent * 10;
			}
			n = n + pd/percent;
			afterDotCount++;
		} 
		p++;
	}
	*num = n;


	// printf("num = %f\n", *num);
}

int main(int argc, char const *argv[])
{
	int i = 0;
	// while(argv[i]!=NULL){
	// 	printf("%s\n", argv[i]);
	// 	++i;
	// }

	char *middleExpress = argv[1];
	// char *middleExpress = "90+(25-11)/34";
	// printf("中缀表达式：%s\n", middleExpress);

	//用于给中缀表达式生成后缀表达式的栈
	char *p = middleExpress; 
	SqStackChar *SC = (SqStackChar *)malloc(sizeof(SqStackChar));
	for(int i=0;i<MAXSIZE;++i){
		SC->data[i] = '0';
	}
	SC->top = -1;

	//字符串栈
	StringStack *reversePolishStack = (StringStack *)malloc(sizeof(StringStack));
	for(int i=0;i<MAXSIZE;++i){
		reversePolishStack->data[i] = NULL;
	}
	reversePolishStack->top = -1;

	//字符串队列
	SqQueue *queue = (SqQueue *)malloc(sizeof(SqQueue));
	InitQueue(queue);

	bool isNumber = false;
	bool afterDot = false;
	int afterDotCount = 0;
	double number = 0;
	while(true){
		if(*p>='0' && *p<='9') {
			if(isNumber){
				if(!afterDot){
					number = number * 10 + *p-48;		
				}else{
					double pd =*p-48; 
					double percent = 10;
					for (int i = 1; i < afterDotCount; ++i)
					{
						percent = percent * 10;
					}
					number = number + pd/percent;
					afterDotCount++;
				}
			}else{
			 	isNumber = true;
			 	number = *p-48;
			}
		}else if(*p=='.') {
			afterDot =true;
			afterDotCount = 1;
			p++;
			continue;

		}else{
			if(isNumber){
				String numberStr = (String)malloc(20*sizeof(char));
				sprintf(numberStr, "%f", number);
				// printf("%f\n", number);
				// printf("%s\n", numberStr);
				StringStackPush(reversePolishStack, numberStr);
				EnQueue(queue,numberStr);
				number = 0;
				isNumber = false;
				afterDotCount = 0;
				afterDot = false;
				free(numberStr);
			}
			if(*p=='+'||*p=='-'||*p=='*'||*p=='/'||*p=='('||*p==')'){
				if(CharStackEmpty(*SC)){
					CharPush(SC, p);
				}else{
					if(*p=='+'||*p=='-'){
						char* top = (char*)malloc(sizeof(char));
						while(!CharStackEmpty(*SC)){
							CharGetTop(SC,top);
							if(*top=='('){ 
								break;
							}
							CharPop(SC,top);
							// printf("%c\n",*top);
							String topStr = (String)malloc(2*sizeof(char));
							topStr[0]=*top;
							topStr[1]='\0';
							StringStackPush(reversePolishStack, topStr);
							EnQueue(queue,topStr);
							// printf("%s\n", topStr);
							free(topStr);
						}
						if(top!=NULL){	//需手动释放top
							free(top);
							top = NULL;
						}
						CharPush(SC, p);
					} else if(*p=='('||*p==')'){
						if(*p=='(')
							CharPush(SC, p);
						else{
							char* top = (char*)malloc(sizeof(char));
							while(!CharStackEmpty(*SC)){
								CharGetTop(SC,top);
								if(*top=='('){
									CharPop(SC,top);
									break;
								}
								CharPop(SC,top);
								// printf("%c\n",*top);
								String topStr = (String)malloc(2*sizeof(char));
								topStr[0]=*top;
								topStr[1]='\0';
								StringStackPush(reversePolishStack,topStr);
								EnQueue(queue,topStr);
								// printf("%s\n", topStr);
								free(topStr);
							}
							if(top!=NULL){	//需手动释放top
								free(top);
								top = NULL;
							}	
						}



					}else { //当前符号是乘除
						char* top = (char*)malloc(sizeof(char));
						CharGetTop(SC,top);
						while(*top=="*"&&*top=="/"){ 
							if(!CharStackEmpty(*SC)){
								CharGetTop(SC,top);
								if(!(top=="*"&&top=="/"))
									break;
								CharPop(SC,top);
								// printf("%c\n",top); 

								String topStr = (String)malloc(2*sizeof(char));
								topStr[0]=*top;
								topStr[1]='\0';
								StringStackPush(reversePolishStack, topStr);
								EnQueue(queue,topStr);
								// printf("%s\n", topStr);
								free(topStr);
							}else{
								free(top);
								top = NULL;
							}
						}
						if(top!=NULL){	//需手动释放top
							free(top);
							top = NULL;
						}
						CharPush(SC, p);
					}
				}
			}else{
				printf("非法字符%c\n",*p);
			}
		}
		p = p+1;
		if(*p=='\0'){
			if(isNumber){
				// printf("%f\n", number);
				String numberStr = (String)malloc(20*sizeof(char));
				sprintf(numberStr, "%f", number);
				// printf("%s\n", numberStr);
				StringStackPush(reversePolishStack, numberStr);
				EnQueue(queue,numberStr);
				number = 0;
				isNumber = false;
				free(numberStr);
			}

			char* top = (char*)malloc(sizeof(char));
			while(!CharStackEmpty(*SC)){
				CharPop(SC,top);
				// printf("%c\n",*top);
				if(top==NULL)
					break;

				String topStr = (String)malloc(2*sizeof(char));
				topStr[0]=*top;
				topStr[1]='\0';
				StringStackPush(reversePolishStack, topStr);
				EnQueue(queue,topStr);
				// printf("%s\n", topStr);
				free(topStr);

			}

			if(top!=NULL)
				free(top);
			break; //break while(true)
		}

	}


	String string = (String)malloc(20*sizeof(char)); 
	// printf("reversePolishStack :");
	while(!StringStackEmpty(*reversePolishStack)){
		StringStackPop(reversePolishStack,string);
		if(string==NULL)
			break;

		// printf("%s ", string);

	}
	DestroyStringStack(reversePolishStack);

	printf("\n");
	//printf("queue :");

	//字符串栈
	StringStack *calculateStack = (StringStack *)malloc(sizeof(StringStack));
	for(int i=0;i<MAXSIZE;++i){
		calculateStack->data[i] = NULL;
	}
	calculateStack->top = -1;


	double result = 0;
	while(!QueueEmpty(*queue)){
		Dequeue(queue,string);
		if(StringStackEmpty(*calculateStack)){
			StringStackPush(calculateStack,string);
			continue;
		}
		if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'){
			String op2 =  (String)malloc(20*sizeof(char));
			StringStackPop(calculateStack,op2);
			String op1 =  (String)malloc(20*sizeof(char));
			StringStackPop(calculateStack,op1);
			double* num1 = (double *)malloc(sizeof(double));
			double* num2 = (double *)malloc(sizeof(double));
			strtodouble(op1,num1);
			strtodouble(op2,num2);
			// printf("parse %s to %f\n",op1,*num1);
			// printf("parse %s to %f\n",op2,*num2);
			if(string[0]=='+'){ 
				result = *num1+*num2;
				// printf("%f + %f = %f\n",*num1,*num2, result);
			}
			if(string[0]=='-'){
				result = *num1-*num2;
				// printf("%f - %f = %f\n",*num1,*num2, result);
			}
			if(string[0]=='*'){
				result = *num1**num2;
				// printf("%f * %f = %f\n",*num1,*num2, result);
			}
			if(string[0]=='/'){
				result = (*num1)/(*num2);
				// printf("%f / %f = %f\n",*num1,*num2, result);
			}


			String numberStr = (String)malloc(20*sizeof(char));
			sprintf(numberStr, "%f", result); 
			StringStackPush(calculateStack, numberStr); 

			free(op1);
			free(op2);
			free(num1);
			free(num2);
			free(numberStr);

		}else{
			StringStackPush(calculateStack,string);
		}
		
	}
	DestroyStringStack(calculateStack);
	DestroyQueue(queue);


	if(string!=NULL)
		free(string);
	
	// printf("\n");
	printf("%s = %f\n",middleExpress, result);
	printf("\n");
	return 0;
		
}